//假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 
//
// 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？ 
//
// 注意：给定 n 是一个正整数。 
//
// 示例 1： 
//
// 输入： 2
//输出： 2
//解释： 有两种方法可以爬到楼顶。
//1.  1 阶 + 1 阶
//2.  2 阶 
//
// 示例 2： 
//
// 输入： 3
//输出： 3
//解释： 有三种方法可以爬到楼顶。
//1.  1 阶 + 1 阶 + 1 阶
//2.  1 阶 + 2 阶
//3.  2 阶 + 1 阶
// 
// Related Topics 动态规划


//leetcode submit region begin(Prohibit modification and deletion)

/*
* 查看解答前的思考：
*   1. 结果需要的是方法数量而不是过程
*       就人的正常思维来讲，首先是一步步走，然后逐渐用“2步”去替换（使用1,2,3,4...个“2步”），知道有可能得全使用“2步”
*       且1+2与2+1不同
*   2. 第一反角出除了1中的思维外没有什么好方法，这种“替换”思想看起来不好表达，因为是week1，要向数组靠拢。
*       最基本的方法可以用元素全为1的数组进行表达，（下标+1）就是指每一步，每个下标对应值为1或2
*       根据“替换”思想，相邻的2个1可以被替换为1个2，且1+2与2+1不同（有序）,但下一级的“替换”，每个2步中间可以有间隙
*
*       双指针。
*       每个双指针为一组，第一遍用1组双指针“走”，第二遍用组双指针“走”，直到达到该数组对双指针的最大容纳数量
*       i从“跨度”的右端开始，以每次一位的速度向右端行进，每行进一步就多一种解法
*
*       但是有间隔这就难办了，
*       虽说twoStepsMaxNum = n/2可以计算出最多可以容纳几个“2步”，但有间隙不容易对solutionNums进行计数。
*
*       1个“2步”用单循环能累计出1个“2步”时的solutionNums，
*       那么，2个“2步”的走法（包括间歇和不间歇）就可以双循环进行累计
*       如此类推，n个“2步”的走法用n重循环进行累计。
*
*       但是这也太暴力了且自己不太会让循环体再次自我循环。。。嵌套？
*       就算写出来了时间复杂度爆炸好吧。
* */

/*
* 查看解答后的思考：
*   1. 超哥的思路更加贴近数组，我没找到规律就是因为还不够“贴近数组”
*       因为超哥是将数组的下标利用起来的，而我是“进行替换”，与可用的数据---下标，没有相结合。也是“子问题”找得太远
*
*   2. 数学递归法->斐波那契数列->计算fibonacci求项的方法->
*       a.无缓存，暴力傻循环
*       b.逐渐累加，泛化，找一般规律，数学归纳法
*
*   3. 基本思想1---懵逼的时候怎么办：(前有误区和加速的核心思想)
*       a. 能不能暴力？
*       b. 从简单开始思考，最基本的情况是什么。
*       c. 找 重复子问题，逐渐到数学归纳法
*       （题目作为题目，说明其本身就是可重复的，都是可以通过拆分和建模，找到“子问题”的，
*        掌握这种思维后，后面的回溯、分治，动态规划、递归）
* */

class Solution70 {

    public int climbStairs(int n) {
        /*
        * 方法一，自己未想出来*/
//        int solutionNums=0;
//        int[] stair = new int[n];
//        int twoStepsMaxNum = n/2;
//        int[] stepSolutionoftwo;//ccc
//
//        //i从“跨度”的右端开始，以每次一位的速度向右端行进，每行进一步就多一种解法
//        for (int i=2; i<stair.length; i++){
//            solutionNums++;
//        }
//        return solutionNums;

        /*
        * 方法二，2.a.1,数组*/
        //因为最后要求的fn的值，且fn=f(n-1)+f(n-2)---即，fn可以由数组的最后两位相加得到
        //为了保存fn的结果，要开辟长度为n+1的数组
//        int[] solutionNums = new int[n+1];
//        solutionNums[1]=1;
//
//        if (n>1){
//            //这里不能无判定就赋值，如果n为1，那么直接赋值会越界
//            solutionNums[2]=2;
//        }
//
//        for (int i=3; i<=n; i++){
//            solutionNums[i]=solutionNums[i-1]+solutionNums[i-2];
//        }
//        //注意返回的是solutionNums[n]，而不是数组中的最后一位solutionNums[n-1]，原因见上方注释
//        return solutionNums[n];
        /*
        * 耗时0ms左右（100%），使用内存35.9M（5%）*/

        /*
         *方法二，2.a。2，递归直出fibonacci */
        if (n<=2){
            return n;
        }else{
            return climbStairs(n-1)+climbStairs(n-2);
        }
        /*
        * 这个方法第一次自己写的时候报错：java.lang.StackOverflowError
        * 说明“抛出这个错误表明应用程序因为深递归导致栈被耗尽了”
        * 原因是一开始写的是if(n==1){return 1;},这就导致当climbStairs(n-2)==climbStairs(2)时递归程序缺失最基础的信息。
        * 另外为了简洁，选择if(n<=2){return n;}是个不错的选择。
        * 当输入45时超时,IntelliJ本地测试运行时间为4229ms*/


        /*
        * 方法二，2.b。最快求项法---迭代循环
        * 嵌套内部做了很多重复的计算且尾递归可以用循环来解决*/
//        int f1=1;
//        int f2=2;
//        int fn=0;
//        if (n<=2){
//            return n;
//        }else{
//            for (int i=3; i<=n; i++){
//                //斐波那契数列第n项等于前一个数(下标n-1)+前前一个数(下标n-2)
//                fn=f1+f2;
//                //当前循环所得的斐波那契数的前一个数，作为下次循环的前前一个数
//                f1=f2;
//                //循环嵌套，当前循环所得的斐波那契的数，作为下次循环的前一个数
//                f2=fn;
//            }
//        }
//        return fn;
        /*
        * 耗时0ms左右（100%），使用内存36.7M（5%）*/
    }
}
//leetcode submit region end(Prohibit modification and deletion)
